package 回溯;

import java.util.ArrayDeque;
import java.util.Queue;

//https://www.nowcoder.com/practice/185a87cd29eb42049132aed873273e83?tpId=196&tqId=37049&ru=/exam/oj
/*
第一道面试题怎么说呢，面试时候咋就没往简单想亏死了
 */
public class 二叉树根节点到叶子节点的所有路径和 {
    public int sumNumbers(TreeNode root) {
        // write code here
        return fun_DFS(root , 0);
        //return fun_BFS(root);
    }
    public int fun_DFS(TreeNode root , int num){
        if (root == null){
            return 0;
        }
        //num用来记录当前路到目前位置的和
        num = num*10 + root.val;
        //到叶子节点了当前路的值都计算完保存在num返回当前值（这个值num）
        if (root.left == null && root.right == null){
            return num;
        }else{
            return fun_DFS(root.left , num) + fun_DFS(root.right , num);
        }
    }
    public int fun_BFS (TreeNode root) {
        if (root == null){
            return 0;
        }
        int num = 0;
        // 定义两个队列，一个存放当前节点，一个存放截止当前节点是num的值
        Queue<TreeNode> queNd = new ArrayDeque<>();
        Queue<Integer> queVal = new ArrayDeque<>();
        //初始化
        queNd.offer(root);
        queVal.offer(root.val);
        //队列操作
        while (!queNd.isEmpty()){
            TreeNode cur = queNd.poll();
            //val值是截止当前节点之前之前，所在路的和，这很重要千万不要从cur.val取值
            int val = queVal.poll();
            if (cur.left == null && cur.right == null){
                num = num + val;
            }
            if (cur.left != null){
                queNd.offer(cur.left);
                queVal.offer(val * 10 + cur.left.val);
            }
            if (cur.right != null){
                queNd.offer(cur.right);
                queVal.offer(val * 10 + cur.right.val);
            }
        }
        return num;

    }

    //题目给定二叉树
    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
    }
}

